package org.example.arrayDemo;

import java.util.Arrays;

/**
 * 插入法排序
 * 动画演示：https://zhuanlan.zhihu.com/p/250327672
 */
public class InsertionSort {
    // 插入法排序
    public static void insertionSort(int[] arr) {
        // 从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的
        for (int i = 1; i < arr.length; i++) {

            // 记录要插入的数据
            int tmp = arr[i];

            // 从已经排序的序列最右边的开始比较，找到比其小的数
            int j = i;
            while (j > 0 && tmp < arr[j - 1]) {
                arr[j] = arr[j - 1];
                j--;
            }

            // 存在比其小的数，插入
            if (j != i) {
                arr[j] = tmp;
            }
        }
    }


    // 入口类
    public static void main(String[] args) {
        int testTime = 500000;
        int maxSize = 100; // 随机数组的长度0～100
        int maxValue = 100;// 值：-100～100


        int[] arr = Utils.generateRandomArray(maxSize, maxValue);
        Utils.printArray(arr);
        insertionSort(arr);
        Utils.printArray(arr);
    }
}
